package hot;

import java.util.Stack;

public class sier {
    public static int trap(int[] nums) {
        //动态规划解法
//        int n=nums.length;
//        int sum=0;
//        //创建两个数组，分别记录左边的最大值和右边的最大值
//        int[] leftMax=new int[n];
//        int[] rightMax=new int[n];
//        for(int i=1;i<n;i++){
//            leftMax[i]=Math.max(nums[i-1],leftMax[i-1]);
//        }
//        for(int i=n-2;i>=0;i--){
//            rightMax[i]=Math.max(nums[i+1],rightMax[i+1]);
//        }
//        for(int i=0;i<n;i++){
//            int res=Math.min(leftMax[i],rightMax[i]);
//            if(res<=nums[i]){
//                sum=sum+0;
//            }else{
//                sum=sum+res-nums[i];
//            }
//        }
//        return sum;
        int n=nums.length;
        int sum=0;
        Stack<Integer> stack=new Stack<>();
        stack.push(-1);
        for(int i=0;i<n;i++){
            while(stack.peek()!=-1&&nums[i]>nums[stack.peek()]){
                int m=stack.pop();
                int width=i-stack.peek()-1;
                if(stack.peek()==-1){
                    break;
                }
                int h=Math.min(nums[i],nums[stack.peek()])-nums[m];
                sum=sum+width*h;
            }
            stack.push(i);
        }
        return sum;
    }

    public static void main(String[] args) {
        int[] nums={4,2,0,3,2,5};
        int trap = trap(nums);
        System.out.println(trap);


    }
}
